using System;

namespace LeetCode {
    public class dpMatch {
        bool[, ] dp;
        public bool dpdownMatch (int i, int j, string src, string ptn) {
            bool ans;
            if (j == ptn.Length) {
                ans = i == src.Length;
            } else {
                bool curMatch = (src[i] == ptn[j]) || ptn[j] == '.';
                if (j + 1 < ptn.Length && ptn[j + 1] == '*') {
                    ans = dpdownMatch (i, j + 2, src, ptn) || (dpdownMatch (i + 1, j, src, ptn) && curMatch);
                } else {
                    ans = dpdownMatch (i + 1, j + 1, src, ptn);
                }
            }
            dp[i, j] = ans;
            return ans;
        }
        public bool isMatch (string text, string pattern) {
            dp = new bool[text.Length + 1, pattern.Length + 1];
            return dpdownMatch (0, 0, text, pattern);
        }
        public bool isupMatch (string text, string pattern) {
            bool[, ] memo = new bool[text.Length + 1, pattern.Length + 1];
            memo[text.Length, pattern.Length] = true;

            for (int i = text.Length; i >= 0; i--) {
                for (int j = pattern.Length - 1; j >= 0; j--) {
                    bool curMatch = (i < text.Length && (pattern[j] == text[i] || pattern[j] == '.'));
                    if (j + 1 < pattern.Length && pattern[j + 1] == '*') {
                        memo[i, j] = memo[i, j + 2] || curMatch && memo[i + 1, j];
                    } else {
                        memo[i, j] = curMatch && memo[i + 1, j + 1];
                    }
                }
            }
            return memo[0, 0];
        }
    }
}